#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣222. 完全二叉树的节点个数
// 【难度】中等
// 【提交】2025.9.25 https://leetcode.cn/problems/count-complete-tree-nodes/submissions/666005133/
// 【标签】树；二分查找；位运算

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

const auto _ = std::cin.tie(nullptr)->sync_with_stdio(false);
#define LC_HACK
#ifdef LC_HACK
const auto __ = []() {
    struct ___ {
        static void _() { std::ofstream("display_runtime.txt") << 0 << '\n'; }
    };
    std::atexit(&___::_);
    return 0;
}();
#endif

class Solution_LC0222 {
public:
    bool find(TreeNode* root, int level, int k) {
        int bits = 1 << (level - 1);
        TreeNode* node = root;
        while (node != nullptr && bits > 0) {
            node = (!(bits & k)) ? node->left : node->right;
            bits >>= 1;
        }
        return node != nullptr;
    }
    
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        
        int level = 0;
        TreeNode* node = root;
        while (node->left != nullptr) {
            level++;
            node = node->left;
        }
        
        int low = 1 << level, high = (1 << (level + 1)) - 1;
        
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            find(root, level, mid) ? low = mid : high = mid - 1;
        }
        return low;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个完全二叉树的根节点root，求出该树的节点个数。
 * 完全二叉树的定义：除最后一层外，其余层都是满的，并且最后一层的节点都靠左排列。
 * 模型：利用完全二叉树的性质，结合二分查找和位运算高效计算节点数。
 * 
 * 二、标准解法状态设计
 * 1. 先计算树的深度（通过一直向左遍历）。
 * 2. 最后一层的节点编号范围是[2^level, 2^(level+1)-1]。
 * 3. 使用二分查找确定最后一个存在的节点编号。
 * 4. 对于每个候选编号，利用二进制表示从根节点导航到该位置。
 * 
 * 三、你的实现思路
 * 使用二分查找法确定最后一层有多少个节点，利用位运算高效导航到指定节点。
 * 
 * 四、逐行注释（带细节提醒）
 * bool find(TreeNode* root, int level, int k) { // 检查第k个节点是否存在
 *     int bits = 1 << (level - 1); // 从最高位开始
 *     TreeNode* node = root;
 *     while (node != nullptr && bits > 0) {
 *         node = (!(bits & k)) ? node->left : node->right; // 根据二进制位选择方向
 *         bits >>= 1; // 移动到下一位
 *     }
 *     return node != nullptr; // 返回节点是否存在
 * }
 * 
 * int countNodes(TreeNode* root) {
 *     if (root == nullptr) return 0; // 空树处理
 *     
 *     int level = 0; // 计算深度
 *     TreeNode* node = root;
 *     while (node->left != nullptr) {
 *         level++;
 *         node = node->left;
 *     }
 *     
 *     int low = 1 << level, high = (1 << (level + 1)) - 1; // 最后一层节点范围
 *     while (low < high) { // 二分查找
 *         int mid = (high - low + 1) / 2 + low; // 防止溢出
 *         find(root, level, mid) ? low = mid : high = mid - 1;
 *     }
 *     return low; // 返回节点总数
 * }
 * 
 * 五、正确性证明
 * 完全二叉树的特性保证了我们可以使用二进制表示来导航到任意节点。
 * 二分查找的正确性基于：如果某个节点存在，那么它左边的所有节点也都存在。
 * 因此，我们可以找到最后一个存在的节点，其编号就是节点总数。
 * 
 * 六、复杂度
 * 时间：O(log² n)，其中n是节点数。
 *     计算深度需要O(log n)，二分查找需要O(log n)次迭代，每次find需要O(log n)。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 利用完全二叉树的性质，算法效率高；
 *   - 结合了二分查找和位运算，思路巧妙；
 *   - 代码实现简洁，避免了递归或层次遍历的空间开销。
 * 缺点：
 *   - 算法理解起来有一定难度；
 *   - 对于非完全二叉树不适用；
 *   - 调试代码可能影响在线评测。
 * 
 * 八、改进建议
 * 1. 可以添加空指针检查：if (root == nullptr) return 0;
 * 2. 使用更明确的变量名（如 depth 代替 level）来增强可读性；
 * 3. 对于在线评测，可以移除调试代码；
 * 4. 可以考虑添加注释解释二进制导航的原理。
 * 
 * 九、一句话总结
 * 通过二分查找和位运算巧妙利用完全二叉树的性质，你的实现高效且优雅，
 * 展现了利用数据结构特性优化算法效率的能力。
 */